package 二叉树;

import java.util.*;

public class BinaryTree<E extends Comparable<E>> {

    static class Node <E>{
        Node<E> left;
        Node<E> right;
        E val;

        public Node(E val) {
            this.val = val;
        }
    }
    public Node<E> root;

    /**
     * 遍历思路获得结点个数
     */
    public int size() {
        int n=size;
        size=0;
        return n;
    }
    //获取树中结点的个数
    public int size(Node<E> root) {
        if(root == null) {
            return 0;
        }
        return 1+size(root.left)+size(root.right);
    }
    /**
     * 前序遍历非递归实现
     * @param root
     */
   public void preOrder1(Node <E> root){
        if(root==null) {
            return;
        }
        Deque<Node<E>> stack=new LinkedList<>();
       Node<E> cur= root;
       Node<E> top=null;
       Node<E> prev=null;
       //记录栈的前一个结点
       while (cur!=null || !stack.isEmpty() ) {
           //只要cur为空就让cur走弹出结点的右边
           while (cur!=null ) {
               //难点，你怎么知道走左边还是右边
               stack.push(cur);
               System.out.print(cur.val+" ");
               cur=cur.left;
           }
           //左边结点为空弹出栈顶元素
           top=stack.pop();
           cur=top.right;
       }
       System.out.println();
    }
    // 前序遍历
    void preOrder(Node <E> root){
        if(root==null) {
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    // 中序遍历
    void inOrder(Node<E>root){
        if(root==null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    /**
     * 非递归中序遍历
     * @param root
     */
    void inOrder1(Node<E>root){
        if(root==null) {
            return;
        }
        Deque<Node<E>> stack=new LinkedList<>();
        Node<E> cur= root;
        Node<E> top=null;
        while (cur!=null || !stack.isEmpty() ) {
            //只要cur为空就让cur走弹出结点的右边
            while (cur!=null ) {
                //难点，你怎么知道走左边还是右边
                stack.push(cur);
                cur=cur.left;
            }
            //左边结点为空弹出栈顶元素
            top=stack.pop();
            System.out.print(top.val+" ");
            cur=top.right;
        }
        System.out.println();
    }
    // 后序遍历
    void postOrder(Node <E> root){
        if(root==null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    /**
     * 后续遍历非递归
     * @param root
     */
    void postOrder1(Node <E> root){
        if(root==null) {
            return;
        }
        Deque<Node<E>> stack=new LinkedList<>();
        Node<E> cur= root;
        Node<E> top=null;
        Node<E> prev=null;
        //记录栈的前一个结点
        while (cur!=null || !stack.isEmpty() ) {
            //只要cur为空就让cur走弹出结点的右边
            while (cur!=null ) {
                //难点，你怎么知道走左边还是右边
                stack.push(cur);
                cur=cur.left;
            }
            //我需要记录一下cur的位置防止又走一遍
            //左边结点为空弹出栈顶元素
            top=stack.peek();
            if(top.right==null || top.right == prev) {
                prev=stack.pop();
                System.out.print(prev.val+" ");
            }else {
                cur=top.right;
            }
        }
        System.out.println();

    }

    // 获取叶子节点的个数,子问题思路
    public int getLeafNodeCount(Node<E> root){
        if(root==null) {
            return 0;
        }
        if(root.left==null&&root.right==null) {
            return 1;
        }
        //左树叶子结点+右树叶子结点
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }

    // 获取叶子节点的个数,遍历思路

    //遍历思路，求得叶子个数然后再去调用leaf就可以得到叶子的个数
    //叶子个数
    int leaf=0;
    public int getLeafNodeCountPlus(Node<E> root){
        funcGetLeafNodeCountPlus(root);
        return leaf;
    }
    public void funcGetLeafNodeCountPlus(Node<E> root) {
        if(root==null) {
            return ;
        }
        if(root.left==null&&root.right==null) {
            leaf++;
        }
        funcGetLeafNodeCountPlus(root.left);
        funcGetLeafNodeCountPlus(root.right);
    }
    // 子问题思路-求叶子结点个数
    public int funcGetLeafNodeCountPlus1(Node<E> root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        return funcGetLeafNodeCountPlus1(root.left)+funcGetLeafNodeCountPlus1(root.right);
    }
    // 获取第K层节点的个数

    /**
     * 左树的第n层和右树的第n层
     * 遍历
     * @param root k
     * @return int
     */
    public int count;
    int getKLevelNodeCount(Node<E> root,int k){
        funcGetKLevelNodeCount(root,k);
        return count;
    }
    public void funcGetKLevelNodeCount (Node<E> root,int k) {
        if(k==1&&root!=null) {
            count++;
            return;
        }
        if(root==null) {
            return;
        }
        getKLevelNodeCount(root.left,k-1);
        getKLevelNodeCount(root.right,k-1);

    }
    /**
     * 子问题解决求树的第n层的结点
     * @param root k
     * @return int
     */

    int getKLevelNodeCountPlus(Node<E> root,int k){
        if(root==null) {
            return 0;
        }
        if(k==1) {
            return 1;
        }
       return getKLevelNodeCountPlus(root.left,k-1)+ getKLevelNodeCountPlus(root.right,k-1);

    }

    // 获取二叉树的高度

    /**
     * 比较左树和右树的高度
     * @param root
     * @return
     */
   public int getHeight(Node<E> root){
        if(root==null) {
            return 0;
        }
        int a=getHeight(root.left);
        int b=getHeight(root.right);
        //左树高度和右树高度求最大值再+1
        return Math.max(a+1, b+1);

    }
    // 检测值为value的元素是否存在
    public boolean find(Node<E> root, E val){
       if(root==null) {
           return false;
       }
       if(root.val==val) {
           return true;
       }
       //遍历当前结点和左子树和右子树
       boolean a1= find(root.left,val);
       boolean a2 = find(root.right,val);
       return a1||a2;
   }
    //层序遍历
    void levelOrder(Node<E> root){
    //利用队列
        Queue<Node<E>> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> cur=queue.poll();
            System.out.print(cur.val+"");
            if(cur.left!=null)
            queue.offer(cur.left);
            if(cur.right!=null)
            queue.offer(cur.right);
        }
        System.out.println();
    }
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(Node<E> root){
       //队列实现
        Deque<Node<E>> queue=new LinkedList<>();
        queue.offer(root);
        while (queue.peek()!=null){
            Node<E> cur=queue.poll();
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        for (int i = 0; i < queue.size(); i++) {
            if(queue.poll()!=null) {
                return false;
            }
        }
        return true;
    }
    /**
     * 遍历思路获得结点个数
     * @param root
     * @return
     */
    // 获取树中节点的个数
    private  int size;
    // 获取树中节点的个数
    public void sizePlus(Node<E> root) {
        if(root==null) {
            return ;
        }
        size++;
        sizePlus(root.left);
        sizePlus(root.right);

    }
    public Node<E> invertTree(Node<E> root) {
        if(root==null) {
            return null;
        }
        //左树的子树和右树的子树
        Node<E> tmp=root.left;
        root.left=root.right;
        root.right=tmp;
         //swap(root.left,root.right);
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    public boolean isBalanced(Node<E> root) {
        if(root==null) {
            return true;
        }
        // //求高度差
        return getHeight1(root)<=1;
    }
    //求树的高度
    public int getHeight1(Node<E> root){
        if(root==null) {
            return 0;
        }
        int a=getHeight1(root.left);
        //如果拿到的值是负数直接返回负数
        if(a<0) {
            return a;
        }
        int b=getHeight1(root.right);
        if(b<0) {
            return b;
        }
        //左树高度和右树高度求最大值再+1
        if(Math.abs(a-b)<=1) {
            return Math.max(a+1,b+1);
        }else {
            return -2;
        }

    }

    /**
     *
     * 根据前序遍历字符串创建二叉树
     */
   public int i=0;
    public  Node<Character> createTree(String str ) {
        Node<Character> treeNode=null;
        if(str.charAt(i)!='#') {
            treeNode=new Node<Character>(str.charAt(i));
            i++;
            treeNode.left=createTree(str);
            treeNode.right=createTree(str);
            return  treeNode;
        }else {
            i++;
            return null;
        }
    }
    //找公共祖先
    public Node<E> lowestCommonAncestor(Node<E> root, Node<E> p, Node<E> q) {
        //利用栈
        Deque<Node<E>> stack1= new LinkedList<>();
        Deque<Node<E>> stack2= new LinkedList<>();

        //创建栈
        lowestCommonAncestorFunc(root,stack1,p);
        lowestCommonAncestorFunc(root,stack2,q);

        int size=stack1.size()-stack2.size();
        //如果stack1的结点比stack2的结点多
        //那么先走差值
        while (size>0) {
            size--;
            stack1.pop();
        }
        //同上
        while (size<0){
            size++;
            stack2.pop();
        }
        //两个栈一起弹
        while (stack1.peek()!=stack2.peek()) {
            stack1.pop();
            stack2.pop();
        }
        return stack1.pop();
    }
    //创建栈
    public boolean lowestCommonAncestorFunc(Node<E> root,Deque<Node<E>> stack,Node<E> val) {
        if(root == null) {
            return false;
        }
        //先将当前的结点添加到栈
        stack.push(root);
        //如果找到了返回true
       if(root == val) {
           return true;
       }
        //来左边找
       boolean p1= lowestCommonAncestorFunc(root.left,stack,val);
        //右边找
       boolean p2 = lowestCommonAncestorFunc(root.right,stack,val);
       //如果两边都没找到弹出
       if(!p1&&!p2) {
           stack.pop();
           return  false;
       }else {
           //有一边找到了
           return true;
       }
    }
    public void tree2str1(StringBuilder str,Node<E> root) {
        if(root == null) {
            return;
        }
        str.append(root.val);
        //左边不为空加左括号
        if(root.left!=null) {
            str.append('(');
            tree2str1(str,root.left);
            //返回后加右括号
            str.append(')');
        }else if(root.right!=null) {
            //左边为空右边不为空加小括号
            str.append("()");
        }
        if(root.right!=null) {
            str.append('(');
            tree2str1(str,root.right);
            str.append(')');
        }

    }
    public String tree2str(Node<E> root) {
        //树走完了+右括号
        //左右都为空不加
        //左不为空右为空不加
        //左为空右不为空加（）
        StringBuilder stringBuilder=new StringBuilder();
        func(stringBuilder,root);
        return stringBuilder.toString();
    }
    public void func(StringBuilder str,Node<E> root) {
        if(root == null) {
            return;
        }
        str.append(root);
        //左边不为空加左括号
        if(root.left!=null) {
            str.append('(');
            func(str,root.left);
            str.append(')');
            //左边为空右边不为空加小括号
        }else if(root.right!=null) {
            str.append("()");
        }
        if(root.right!=null) {
            str.append('(');
            func(str,root.right);
            str.append(')');
        }

    }  /* public void swap(Node<E> P,Node<E> Q) {
        Node<E> tmp=P;
        P=Q;
        Q=tmp;
    }*/
  /* private List<Integer> list=new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root==null) {
          return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }*/
  /*public List<Integer> preorderTraversal(TreeNode root) {
      List<Integer> list=new LinkedList<>();
      func(root,list);
      return list;
  }
    private void func(TreeNode root,List<Integer> list) {
        if(root==null) {
            return;
        }
        list.add(root.val);
        func(root.left,list);
        func(root.right,list);
    }*/

    /**
     * 利用返回值
     * @param root
     * @return
     */
   /* public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        return func(root);
    }
    //利用返回值
    //1 null 2 3
    private List<Integer> funcPreorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        if(root==null) {
            return list;
        }
        list.add(root.val);
        list.addAll(funcPreorderTraversal(root.left));
        list.addAll(funcPreorderTraversal(root.right));
        return list;
    }*/

}
